package mine.code.question.动态规划;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * n皇后问题 研究的是如何将 n个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * <p>
 * 给你一个整数 n ，返回所有不同的n皇后问题 的解决方案。
 * <p>
 * 每一种解法包含一个不同的n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 * <p>
 * 输入：n = 4
 * 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 * 解释：如上图所示，4 皇后问题存在两个不同的解法。
 *
 * @author caijinnan
 * @date 2019/12/13 11:20
 */
public class N皇后 {

    @Test
    public void run() {
        System.out.println(solveNQueens(4));
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        if (n == 1) {
            result.add(new ArrayList<String>() {{
                add("Q");
            }});
        }
        if (n < 4) {
            return result;
        }
        List<List<Integer[]>> pointIndex = new ArrayList<>();
        String[][] dp = new String[n][n];
        for (String[] strings : dp) {
            Arrays.fill(strings, ".");
        }
        putQ(dp, dp.length, 0, pointIndex, result);
        return result;
    }

    private void putQ(String[][] dp, int length, int y, List<List<Integer[]>> pointIndex, List<List<String>> result) {
        if (length == y) {
            result.add(convert(dp));
            return;
        }
        for (int x = 0; x < dp[y].length; x++) {
            if (checkPoint(pointIndex, x, y)) {
                dp[y][x] = "Q";
                pointIndex.add(setPointIndex(x, y, length));
                putQ(dp, length, y + 1, pointIndex, result);
                dp[y][x] = ".";
                pointIndex.remove(pointIndex.size() - 1);
            }
        }
    }


    private List<String> convert(String[][] dp) {
        List<String> result = new ArrayList<>();
        for (String[] strings : dp) {
            result.add(String.join("", strings));
        }
        return result;
    }

    private List<Integer[]> setPointIndex(int x, int y, int n) {
        List<Integer[]> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            result.add(new Integer[]{x, i});
        }
        for (int i = 0; i < n; i++) {
            result.add(new Integer[]{i, y});
        }
        for (int i = x, j = y; i < n && j < n; i++, j++) {
            result.add(new Integer[]{i, j});
        }
        for (int i = x, j = y; i >= 0 && j < n; i--, j++) {
            result.add(new Integer[]{i, j});
        }
        return result;
    }

    private boolean checkPoint(List<List<Integer[]>> pointIndex, int x, int y) {
        for (List<Integer[]> index : pointIndex) {
            for (Integer[] indexArr : index) {
                if (indexArr[0] == x && indexArr[1] == y) {
                    return false;
                }
            }
        }
        return true;
    }
}
